// https://www.lintcode.com/problem/find-pivot-index/

public class Solution {
    /**
     * @param nums: an array
     * @return: the "pivot" index of this array
     */
    public int pivotIndex(int[] nums) {
        // Write your code here
        int sum = 0;
        int ls = 0, rs = 0;
        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
        }
        for (int i = 0; i < nums.length; ++i) {
            if (i == 0) {
                ls = 0;
            } else {
                ls += nums[i - 1];
            }
            rs = sum - nums[i] - ls;
            if (ls == rs) {
                return i;
            }
        }
        return -1;
    }
}